package xyz.scootaloo.alg.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author flutterdash@qq.com
 * @since 2021/3/21 23:20
 */
public class MergeSort {

    public static int[] sort(int[] arr) {
        if (arr == null)
            throw new NullPointerException();
        if (arr.length <= 1)
            return arr;

        // 准备数据
        int[] tmp = new int[arr.length];
        // 排序
        sortCore(arr, 0, arr.length - 1, tmp);
        // 返回
        return arr;
    }

    /**
     * 1. [9, 7, 4, 6, 2, 1， 7， 3]            将数组进行分割，形成越来越小的子数组
     * 2. [9, 7, 4, 6] [2, 1, 7, 3]
     * 3. [9, 7] [4, 6] [2, 1] [7, 3]
     * 4. [9] [7] [4] [6] [2] [1] [7] [3]      划分到极限后，开始合并
     * 5. [7, 9] [4, 6] [1, 2] [3, 7]          从这个位置开始，每个子数组都是有序的了
     * 6. [4, 6, 7, 9] [1, 2, 3, 7]
     * 7. [1, 2, 3, 4, 6, 7, 7, 9]             合并完后，数组已经都是有序的了
     *
     * @param arr     目标数组
     * @param left    目标数组的子数组的左边界
     * @param right   目标数组的子数组的右边界
     * @param tmp     临时数组
     */
    private static void sortCore(int[] arr, int left, int right, int[] tmp) {
        // 假如左右边界没有碰撞，则进行递归，把数组的一个区间继续分为左右两个子数组
        if (left < right) {
            int mid = (left + right) / 2;
            // 将当前数组区间划分出左子数组
            sortCore(arr, left, mid, tmp);
            // 将当前数组区间划分出右子数组
            sortCore(arr, mid + 1, right, tmp);
            // 合并
            merge(arr, left, mid, right, tmp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {
        int l = left;     // 左子数组的下标
        int r = mid + 1;  // 右子数组的下标
        int tmpIdx = 0;   // 临时数组的下标

        /* 合并两个有序数组
         *  l         r                      Step.1
         * [2, 4, 6] [1, 3, 5]
         * [-, -, -, -, -, -] tmp数组
         *
         * 将 l 和 r 下标对应的值选取最小的那个放入tmp数组，同时移动指针
         *  l         *  r                   Step.2
         * [2, 4, 6] [1, 3, 5]
         * [1, -, -, -, -, -] tmp数组
         *
         *  *  l         r                   Step.3
         * [2, 4, 6] [1, 3, 5]
         * [1, 2, -, -, -, -] tmp数组
         *
         *     l         *  r                Step.4
         * [2, 4, 6] [1, 3, 5]
         * [1, 2, 3, -, -, -] tmp数组
         *
         *     *  l         r                Step.5
         * [2, 4, 6] [1, 3, 5]
         * [1, 2, 3, 4, -, -] tmp数组
         *
         *        l         * r <- 越界，达到条件，退出循环  Step.6
         * [2, 4, 6] [1, 3, 5]
         * [1, 2, 3, 4, 5, -] tmp数组
         */
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                tmp[tmpIdx] = arr[l];
                tmpIdx++;
                l++;
            } else {
                tmp[tmpIdx] = arr[r];
                tmpIdx++;
                r++;
            }
        }

        while (l <= mid) {
            tmp[tmpIdx] = arr[l];
            tmpIdx++;
            l++;
        }

        while (r <= right) {
            tmp[tmpIdx] = arr[r];
            tmpIdx++;
            r++;
        }

        // 重置临时数组下标，将临时数组里已排好序的内容回写到原数组
        tmpIdx = 0;
        while (left <= right) {
            arr[left] = tmp[tmpIdx];
            tmpIdx++;
            left++;
        }
    }

    public static void main(String[] args) {
//        int[] sample = {3, 1, 4, 2, 5, 9};
        int[] sample = {9, 9, 9, 1, 9};
        System.out.println(Arrays.toString(sort(sample)));
    }

}
